package linearstructure.linkedlist.singlelist;

import java.util.Stack;

/**
 * @ author : HyoJoo-W
 * @ createDate : 2021-05-24 16:50
 * @ Description : 单链表
 */
public class SingleLinkedList
{
    //初始化头节点
    private final HeroNode head = new HeroNode(0, "", "");

    public HeroNode getHead()
    {
        return head;
    }

    /**
     * @param heroNode: 英雄节点
     * @return void
     * @Description 尾插法
     **/
    public void add(HeroNode heroNode)
    {
        HeroNode temp = head;
        while (temp.next != null)
        {
            temp = temp.next;
        }
        temp.next = heroNode;
    }

    /**
     * @param heroNode: 插入节点
     * @return void
     * @Description 按照顺序插入
     **/
    public void addByOrder(HeroNode heroNode)
    {
        HeroNode temp = head;
        boolean flag = false;
        while (true)
        {
            if (temp.next == null)
            {
                //已经是最后一个节点
                break;
            }
            if (temp.next.no > heroNode.no)
            {
                //找到插入位置
                break;
            }
            else if (temp.next.no == heroNode.no)
            {
                //待插入节点的编号已经存在
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag)
        {
            System.out.printf("待插入节点编号%d已经存在,", heroNode.no);
        }
        else
        {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

    }

    /**
     * @param
     * @return void
     * @Description 顺序遍历
     **/
    public void list()
    {
        if (head.next == null)
        {
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head.next;
        while (temp != null)
        {
            System.out.println(temp);
            temp = temp.next;
        }
    }

    /**
     * @param
     * @return void
     * @Description 逆序遍历
     **/
    public void reverseList(HeroNode head)
    {
        if (head == null)
        {
            return;
        }
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;
        while (cur != null)
        {
            stack.push(cur);
            cur = cur.next;
        }
        while (stack.size() > 0)
        {
            System.out.println(stack.pop());
        }
    }


    public void update(HeroNode newHeroNode)
    {
        if (head.next == null)
        {
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head.next;
        boolean flag = false;//表示是否找到该节点
        while (true)
        {
            if (temp == null)
            {
                //找到最后一个
                break;
            }
            if (temp.no == newHeroNode.no)
            {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag)
        {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        }
        else
        {
            System.out.printf("没有找到编号为%d的节点", newHeroNode.no);
        }

    }

    public void delete(int no)
    {
        HeroNode temp = head;//找到待删除节点的前一个节点
        boolean flag = false;
        while (true)
        {
            if (temp.next == null)
            {
                break;
            }
            if (temp.next.no == no)
            {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag)
        {
            temp.next = temp.next.next;
        }
        else
        {
            System.out.printf("待删除的节点编号%d不存在", no);
        }
    }

    /**
     * @param
     * @return
     * @Description 统计有效节点个数(不包含头结点)
     **/
    public int getLength(HeroNode head)
    {
        if (head.next == null)
        {
            return 0;
        }
        int length = 0;
        HeroNode cur = head.next;
        while (cur != null)
        {
            length++;
            cur = cur.next;
        }
        return length;
    }

    /**
     * @param
     * @return
     * @Description 查找倒数第k个节点
     **/
    public HeroNode findLastIndexNode(HeroNode head, int index)
    {
        if (head == null)
        {
            return null;
        }
        int size = this.getLength(head);
        if (index <= 0 || index > size)
        {
            return null;
        }
        HeroNode cur = head.next;
        for (int i = 0; i < size - index; i++)
        {
            cur = cur.next;
        }
        return cur;
    }

    /**
     * @param
     * @return
     * @Description 单链表的反转
     **/
    public void reverse(HeroNode head)
    {
        if (head.next == null || head.next.next == null)
        {
            return;
        }
        HeroNode nextNode = null;
        HeroNode cur = head.next;
        HeroNode reverseHead = new HeroNode(0, "", "");
        while (cur != null)
        {
            nextNode = cur.next;//保存原链表的下一个节点

            cur.next = reverseHead.next;//头插法将当前节点插入新链表
            reverseHead.next = cur;

            cur = nextNode;//恢复当前指针
        }
        head.next = reverseHead.next;
    }

}
